class Solution {
public:
  int rob(vector<int>& nums) {

    if(nums.size() == 0){
      return 0;
    }

    if(nums.size() == 1){
      return nums[0];
    }

    // dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
    int n = nums.size();
    int dp[n + 3];
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for(int i = 2; i < n; ++i){
      dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    }

    return dp[n - 1];

  }
};